Hlavní stránka > Výsledky hledání: keywords:"problém online labelingu"
Hledej:
Tipy pro vyhledávaní :: Rozšířené hledání
Hledej ve sbírkách:
Seřadit podle: Zobrazit výsledky: Výstupní formát:
Národní úložiště šedé literatury Nalezeno 2 záznamů.  Hledání trvalo 0.01 vteřin. 
The Online Labeling Problem
 Bulánek, Jan ; Koucký, Michal (vedoucí práce) ; Brodal, Gerth (oponent) ; Iacono, John (oponent)
Setříděné pole je zásadní algoritmický koncept, jehož online varianta je základem pro problém online labelingu. Problém online labelingu je definován následovně. Vstupem je pole velikosti m a posloupnost celých čísel z universa {1,...,r} v libovolném pořadí délky n. Naším úkolem je udržovat všechna přijatá čísla setříděná v poli. Mezi vloženými čísly mohou být mezery. Protože závěrečné pořadí čísel nelze určit, dokud nejsou vložena všechna, je povoleno čísla v poli přesouvat. Cílem je minimalizovat počet přesunů. Ukážeme dva algoritmy, které společně poskytují optimální řešení pro téměř všechny hodnoty m coby funkce n. Dokážeme těsné dolní odhady pro téměř všechny hodnoty m. Zavedeme notaci omezeného universa vstupní množiny čísel a dokážeme dolní odhady i pro tuto variantu. Dokážeme dolní odhady i pro případ randomizovaných algoritmů. Powered by TCPDF (www.tcpdf.org)
Úplný záznam
The Online Labeling Problem
 Bulánek, Jan ; Koucký, Michal (vedoucí práce) ; Brodal, Gerth (oponent) ; Iacono, John (oponent)
Setříděné pole je zásadní algoritmický koncept, jehož online varianta je základem pro problém online labelingu. Problém online labelingu je definován následovně. Vstupem je pole velikosti m a posloupnost celých čísel z universa {1,...,r} v libovolném pořadí délky n. Naším úkolem je udržovat všechna přijatá čísla setříděná v poli. Mezi vloženými čísly mohou být mezery. Protože závěrečné pořadí čísel nelze určit, dokud nejsou vložena všechna, je povoleno čísla v poli přesouvat. Cílem je minimalizovat počet přesunů. Ukážeme dva algoritmy, které společně poskytují optimální řešení pro téměř všechny hodnoty m coby funkce n. Dokážeme těsné dolní odhady pro téměř všechny hodnoty m. Zavedeme notaci omezeného universa vstupní množiny čísel a dokážeme dolní odhady i pro tuto variantu. Dokážeme dolní odhady i pro případ randomizovaných algoritmů. Powered by TCPDF (www.tcpdf.org)
Úplný záznam

Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.
Digitální repozitář :: Hledej :: Nový záznam :: Personalizace :: Nápověda
Powered by Invenio v1.1.2
Spravuje admin.invenio@techlib.cz
Tato stránka je dostupná také v následujících jazycích:
Česky  English